//
// Created by admin on 2022/6/10.
// 152. 乘积最大子数组: https://leetcode.cn/problems/maximum-product-subarray/
//

#include <vector>
#include <algorithm>

using namespace std;

class MaxProduct {
public:
    //动态规划
    int maxProduct(vector<int>& nums) {
        vector<int> maxDp(nums),minDp(nums);
        for (int i = 1; i < nums.size(); ++i) {
            maxDp[i] = max(nums[i],max(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
            minDp[i] = min(nums[i],min(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
        }
        return *max_element(maxDp.begin(),maxDp.end());
    }
};

